// 不相交集（Disjoint Set）
// 也叫并查集(Union/Find Set)
//
// 对N个元素编号0 到 N-1, 初始时每个元素单独为一个集合(树),
// 其DisjointSet[i]表示节点i的父节点, 若为负数, 表示DisjointSet[i]就是树根

#include <stdio.h>

#define N 10 // 所有集合元素总数
typedef int DisjointSet[N]; // 所有集合元素
typedef int SetType;
typedef int ElementType;

// 归并类型
// 1: 随机(root1是新根)
// 2: 按规模(集合大小), 小的归并到大的
// 3: 按树高, 低的树"贴"到高的树上
#define UNION_TYPE 3

// 查找方式
// 1: 普通递归查找
// 2: 路径压缩(其实就是变成了尾递归)
#define FIND_TYPE 3

void Initialize(DisjointSet s) {
    for (int i = 0; i < N; i++) {
        // 按规模归并时, -1表示当前集合只有一个元素
        s[i] = -1; // 所有元素自成一个集合(树), 初始在树根的位置
    }
}

// 两个集合作并集, 合并后root1为新树树根
void Union(DisjointSet s, SetType root1, SetType root2) {
    int tmp;

    #if (UNION_TYPE == 1)
        s[root2] = root1; // root2所在树的根现在是root1
    #elif (UNION_TYPE == 2)
        // s[root]表示s[-N], N为集合元素的个数
        // 所以s[root2] > s[root1], 表示集合2比集合1"规模小"
        // 所以树2要贴到树1上
        if (s[root2] > s[root1]) {
            tmp = s[root2];
            s[root2] = root1;
            s[root1] += tmp; // 更新下集合1的规模
        } else {
            tmp = s[root1];
            s[root1] = root2;
            s[root2] += tmp;
        }
    #elif (UNION_TYPE == 3)
        if (s[root2] < s[root1]) { // 树2比树1高
            s[root1] = root2; // 树1贴到树2上
        } else {
            // 两树等高, 选择树2贴到树1上
            // 树1高度加1
            if (s[root1] == s[root2]) {
                s[root1]--;
            }
            s[root2] = root1;
        }
    #endif
}

// 查找元素x所在的集合(返回树根)
SetType Find(ElementType x, DisjointSet s) {
    if (s[x] < 0) { // s[x]负数, 说明x在树根的位置
        return x;
    }

    #if (FIND_TYPE == 1)
        return Find(s[x], s);
    #elif (FIND_TYPE == 2)
        return s[x] = Find(s[x], s);
    #elif (FIND_TYPE == 3)
        while (s[x] >= 0) {
            x = s[x];
        }
        return x;

    #endif
}


// 判断两个元素是否属于同一个集合(属于同一棵树)
bool Connected(ElementType x, ElementType y, DisjointSet s) {
    return Find(x, s) == Find(y, s);
}

int main(int argc, char *argv[])
{
    // {1, 2} 表示1, 2两个元素在一个集合里
    int testData[][2] = {
        {0, 1},
        {1, 2},
        {2, 4},
        {4, 5},
        {5, 6},
        {6, 8},
        {8, 9}
    };

    DisjointSet s;
    Initialize(s);
    for (int i = 0; i < sizeof(testData) / sizeof(testData[0]); i++) {
        Union(s, Find(testData[i][0], s), Find(testData[i][1], s));
    }

    if (Connected(0, 9, s)) {
        printf("connected\n");
    } else {
        printf("not connected\n");
    }
    return 0;
}
